﻿using System;
using System.Collections.Generic;
using System.Linq;

class QuickSort
{
    static void Main()
    {
        //Exercise 14.
        //Write a program that sorts an array of strings using the quick sort algorithm (find it in Wikipedia).

        //string[] array = {"month", "animal", "school", "mall", "picture", "brown", "domino", "dog", "house", "tango", 
        //                        "number", "oskar", "bill", "kilo", "wish", "jar", "zebra", "rectangle"};
        
        //enter the length and the elements of the array from the console
        Console.Write("Type the length of the array (N):  ");
        int N = int.Parse(Console.ReadLine());
        Console.WriteLine("Type the elements of the array:");
        string[] array = new string[N];
        
        for (int i = 0; i < N; i++)
        {
            array[i] = Console.ReadLine();            
        }
        
        if (array.Length <= 1)
        {
            Console.WriteLine("An array of zero or one elements is already sorted");
            return;
        }

        //print the unsorted array
        for (int i = 0; i < array.Length; i++)
        {
            Console.Write(array[i] + " ");
        }
        Console.WriteLine();
        Console.WriteLine();
               
        List<string> sortedList = array.ToList();
        sortedList = Partition(sortedList);
        foreach (var item in sortedList)
        {
            Console.WriteLine(item);
        }
            

    }
    private static List<string> Partition(List<string> partition)
    {
        List<string> Left = new List<string>();
        List<string> Right = new List<string>();
        if (partition.Count > 0)
        {
            int pivot = GetPivot(partition);
            string pivotString = partition[pivot];
            for (int i = 0; i < partition.Count; i++)
            {
                if (i != pivot)
                {
                    if (string.Compare(partition[i], partition[pivot]) >= 0)
                    {
                        Right.Add(partition[i]);
                    }
                    else
                    {
                        Left.Add(partition[i]);
                    }
                }
            }
            Left = Partition(Left);
            Right = Partition(Right);

            partition.Clear();
            partition.AddRange(Left);
            partition.Add(pivotString);
            partition.AddRange(Right);
        }
        return partition;
    }

    public static int GetPivot(List<string> tempArray)
    {
        Random randomNumber = new Random();
        int[] random = new int[3];
        string[] randomString = new string[3];

        for (int i = 0; i < 3; i++)
        {
            random[i] = randomNumber.Next(0, tempArray.Count);
            randomString[i] = tempArray[random[i]] + i;
        }
        Array.Sort(randomString);
        return random[(randomString[1][randomString[1].Length - 1]) - '0'];
    }

}

